package com.wz.sort;

public class QuickSort {
	static int count = 0;

	public static void doSort(int begin, int end, int... args){
		if (end - begin < 1){
			return;
		}
		int compareValue = args[begin];
//		int compareIndex = sort(compareValue, begin, begin, end, args);
		int compareIndex = theRightSort(begin, end, args);
		doSort(begin, compareIndex - 1, args);
		doSort(compareIndex + 1, end, args);
	}

	public static int sort(int compareValue, int compareValueIndex, int begin, int end, int... args){
		boolean isSorted = true;
		for (int i = end; i > 0; i--) {
			if ((compareValueIndex > i && compareValue < args[i]) || (compareValueIndex < i && compareValue > args[i])){
				args[compareValueIndex] = args[i];
				args[i] = compareValue;
				compareValueIndex = i;
				isSorted = false;
				break;
			}
		}
		if (isSorted){
			args[compareValueIndex] = compareValue;
			return compareValueIndex;
		}
		for (int i = 0; i < args.length; i++) {
			System.out.print(args[i] + ",");
		}
		System.out.println("");
		return sort(compareValue, compareValueIndex, begin, end, args);
	}

	public static int theRightSort(int begin, int end, int... args){
		int left = begin;
		int right = end;

		int compareValue = args[left];

		while (left < right){
			while(left < right){
				if (compareValue > args[right]){
					int tmp = args[left];
					args[left] = args[right];
					args[right] = tmp;
//					right--;
					break;
				}
				right--;
			}
			while(left < right){
				if (compareValue < args[left]){
					int tmp = args[right];
					args[right] = args[left];
					args[left] = tmp;
//					left++;
					break;
				}
				left++;
			}
		}
		return left;
	}

	public static void main(String[] args) {
		//[3, 1, 9, 7, 4, 9, 10, 789, 234, 873, 8574, 221, 12, 885, 64, 2154, 2, 1, 9, 9, 55, 46]
		int[] a = new int[]{70, 1, 9, 7, 4, 9, 10, 789, 234, 873, 2212, 221, 12, 885, 64, 2154, 2, 1, 9, 3, 55, 46};
//		QuickSort.sort(8, 0, 1, a.length-1, a);
//		QuickSort.theRightSort(0, a.length-1, a);
		QuickSort.doSort(0, a.length-1, a);
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + ",");
		}
	}
}